package com.michael.leetcode;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;

public class MinStack_LRC147 {
    /**
     * LCR 147. 最小栈
     * 请你设计一个 最小栈 。它提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
     * 实现 MinStack 类:
     *
     * MinStack() 初始化堆栈对象。
     * void push(int val) 将元素val推入堆栈。
     * void pop() 删除堆栈顶部的元素。
     * int top() 获取堆栈顶部的元素。
     * int getMin() 获取堆栈中的最小元素。
     *
     * 示例 1：
     * 输入：
     * ["MinStack","push","push","push","getMin","pop","top","getMin"]
     * [[],[-2],[0],[-3],[],[],[],[]]
     *
     * 输出：
     * [null,null,null,null,-3,null,0,-2]
     *
     * 解释：
     * MinStack minStack = new MinStack();
     * minStack.push(-2);
     * minStack.push(0);
     * minStack.push(-3);
     * minStack.getMin();   --> 返回 -3.
     * minStack.pop();
     * minStack.top();      --> 返回 0.
     * minStack.getMin();   --> 返回 -2.
     *
     * 提示：
     * -231 <= val <= 231 - 1
     * pop、top 和 getMin 操作总是在 非空栈 上调用
     * push、pop、top 和 getMin 最多被调用 3 * 104 次
     */
    class MinStack {
        private Deque<Integer> deque;
        private Integer min;
        /** initialize your data structure here. */
        public MinStack() {
            deque = new ArrayDeque<>();
        }

        public void push(int x) {
            if (deque.isEmpty()) {
                deque.addFirst(x);
                min = x;
                return;
            }

            if (x < min) {
                min = x;
            }
            deque.addFirst(x);
        }

        public void pop() {

            Integer first = deque.removeFirst();
            if (!Objects.equals(first, min)){
                return;
            }
            min = Integer.MAX_VALUE;
            // 更新最小元素
            int size = this.deque.size();
            for (int i = 0; i < size ; i++) {
                Integer pop = deque.pop();
                min = Math.min(pop, min);
                deque.addLast(pop);
            }
        }

        public int top() {
            return deque.getFirst();
        }

        public int getMin() {
            return min;
        }
    }

    @Test
    public void test(){
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.getMin();
        minStack.pop();
        minStack.top();
         minStack.getMin();
    }
}
